package leecode

func permutation(S string) (result []string) {
	arr := []byte(S)
	path := make([]byte, 0, len(arr))
	used := make([]bool, len(arr))
	var backtracking func()
	backtracking = func() {
		if len(path) == len(arr) {
			temp := make([]byte, len(path))
			copy(temp, path)
			result = append(result, string(temp))
			return
		}
		for i := 0; i < len(arr); i++ {
			if used[i] {
				continue
			}
			used[i] = true
			path = append(path, arr[i])
			backtracking()
			//回溯
			path = path[:len(path)-1]
			used[i] = false
		}
	}
	backtracking()
	return
}
